package org.example;

import java.util.*;

public class Test {


    /*public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        // 走到这里就已经遍历了一次链表了
        // map中已经有了新旧节点地址的关系映射
        // 这个时候就要去填写新节点中的next域和random域
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }*/

    /**
     * 删除单链表中重复的元素
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = prev.next;
        while (cur != null) {
            if (cur.val != val) {
                prev = prev.next;
                //cur = cur.next;
            }else {
                prev.next = cur.next;
                //cur = cur.next;
            }
            //由上面代码合并而来
            cur = cur.next;
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    /**
     * 杨辉三角
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                }else {
                    int val = ret.get(i-1).get(j-1) + ret.get(i-1).get(j);
                    list.add(val);
                }
            }
            ret.add(list);
        }
        return ret;
    }

    /**
     * 旋转数组
     * @param nums
     * @param k
     */
    public void rotate2(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k -1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] array, int i, int j) {
        while (i < j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            i++;
            j--;
        }
    }

    public int removeElement(int[] nums, int val) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }

    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int end1 = m - 1;
        int end2 = n - 1;
        int end =  m + n - 1;
        while (end1 >= 0 && end2 >= 0) {
            if (nums1[end1] >= nums2[end2]) {
                nums1[end--] = nums1[end1--];
            }else {
                nums1[end--] = nums2[end2--];
            }
        }
        //走到这里，可能是nums1数组没走完，也可能是nums2数组没走完
        while (end1 >= 0) {
            nums1[end--] = nums1[end1--];
        }
        while (end2 >= 0) {
            nums1[end--] = nums2[end2--];
        }
    }

    /**
     * 旋转数组
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        for (int i = 0; i < k; i++) {
            int end = nums[n-1];
            for (int j = n - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = end;
        }
    }

    /**
     * 消失的数字
     * @param nums
     * @return
     */


    public int missingNumber2(int[] nums) {
        int data = 0;
        for (int i = 0; i < nums.length; i++) {
            data ^= nums[i];
            data ^= i;
        }
        data ^= nums.length;
        return data;
    }

    public int missingNumber1(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return (((1 + nums.length) * nums.length) / 2) - sum;
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 1; j < array.length - i - 1; j++) {
                if (array[i] > array[i + 1]) {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    flag = true;
                }
                if (flag == false) {
                    return;
                }
            }
        }
    }

    public static void main4(String[] args) {
        int[] array = { 5, 4, 3, 2, 1 };
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }



    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val != val) {
                prev = prev.next;
                cur = cur.next;
            }else {
                prev.next = cur.next;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    public List<List<Integer>> generate(int numRows) {
        if (numRows <= 0) {
            return null;
        }
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1);
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            // 这是开头
            list.add(1);
            // 这是中间
            for (int j = 1; j < i; j++) {
                List<Integer> preRow = ret.get(i-1);
                int val = preRow.get(j-1) + preRow.get(j);
                list.add(val);
            }
            //这是结尾
            list.add(1);
            ret.add(list);
        }
        return ret;
    }


    public String toLowerCase(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= 'A' && ch <='Z') {
                ch += 32;
            }
            sb.append(ch+"");
        }
        return sb.toString();
    }

    public int countSegments(String s) {
        s = s.trim();
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int count = 0;
        String[] result = s.split(" ");

        for (String str : result) {
            if (str.isEmpty()) {
                continue;
            }
            count++;
        }
        return count;
    }

    public static void main3(String[] args) {
        String s = "Hello, my name is John";
        String[] result = s.split(" ");
        for (String str : result) {
            System.out.println(str);
        }
    }

    public int firstUniqChar(String s) {
        //1.申请一个计数数组
        int[] count = new int[26];
        //2.遍历字符串将字符出现的次数放到计数数组中
        for (int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            count[ch - 'a']++;
        }
        //3.再次遍历这个字符串，计数数组中第一次出现 1 的字符就是第一个唯一字符
        for (int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if (count[ch - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

    //Set使用
    public static void main2(String[] args) {
        Set<String> strings = new TreeSet<>();
        strings.add("hello");
        strings.add("abcd");
        strings.add("def");
        strings.add("def");//这里TreeSet底层是TreeMap，每次存储元素放到map的key上
        // strings.clear();
        Iterator<String> iterator = strings.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    //Map使用
    public static void main1(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("hello",2);//相当于往搜索树当中 插入数据  他是和key比较的
        map.put("abcd",3);
        map.put("abcde",4);
        map.put("abcdf",5);
        map.put("abcdfg",6);
        map.put("abcdfg",61);//相同的key 会更新val值

        Set<String> set = map.keySet();
        System.out.println(set);

        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println("key: " + entry.getKey() + " " + "val: " + entry.getValue());
        }
        map.remove("abcd");

        System.out.println(map.getOrDefault("abcd",9999));

        System.out.println("dasdads");
    }


    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1, str2);
        }
    }

    /**
     *
     * @param str1 键盘没坏输入的文字
     * @param str2 实际输入的文字
     */
    private static void func(String str1, String str2) {
        Set<Character> set = new HashSet<>();
        for (char c : str2.toUpperCase().toCharArray()) {
            set.add(c);
        }
        Set<Character> setBroken = new HashSet<>();
        for (char c : str1.toUpperCase().toCharArray()) {
            if (!set.contains(c) && !setBroken.contains(c)) {
                setBroken.add(c); // 把坏了的键放在单独的集合中中
                System.out.print(c);
            }
        }
    }


    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            }else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        // 2. 按照出现次数排序，创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 当出现次数相同时，题目要求按照字典序输出，所以不能采用建小堆入栈的方式，而是要用建大堆的方式入栈
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 3. 遍历Map，将元素放入小根堆
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    //如果单词出现次数相同，则按照字典序放入小根堆 则放key小的
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if (top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }

        }
        //4.将堆中的元素取出，放入List中
        List<String> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            res.add(s);
        }
        Collections.reverse(res);
        return res;
    }

}
